package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * 对链表进行插入排序
 * 算法：链表
 *
 * @author yezh
 * @date 2023/1/11 22:06
 */
public class NC244 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1585, new ListNode(766, new ListNode(-821, new ListNode(-153, new ListNode(1442, null)))));
        ListNode listNode = new NC244().insertionSortList(head);
        System.out.println(listNode.val);
    }

    public ListNode insertionSortList(ListNode head) {
        ListNode first = head, next = head.next;
        first.next = null;
        head = next;
        while (head != null) {
            next = head.next;
            if (head.val <= first.val) {
                head.next = first;
                first = head;
            } else {
                ListNode cur = first, pre = cur;
                while (cur != null && cur.val < head.val) {
                    pre = cur;
                    cur = cur.next;
                }
                head.next = pre.next;
                pre.next = head;
            }
            head = next;
        }
        return first;
    }

}
